package practise.leetcode.q174;

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        final int minHP = 1;
        int rows = dungeon.length;
        int cols = 0;
        if (rows > 0) {
            cols = dungeon[0].length;
        }

        if (rows == 0 || cols == 0) {
            return minHP;
        }

        int[][] dp = new int[rows][cols];
        dp[rows - 1][cols - 1] = minHP - dungeon[rows - 1][cols - 1];
        setMinHP(dp, rows - 1, cols - 1);

        for (int row = rows - 2; row >= 0; row--) {
            dp[row][cols - 1] = dp[row + 1][cols - 1] - dungeon[row][cols - 1];
            setMinHP(dp, row, cols - 1);
        }

        for (int col = cols - 2; col >= 0; col--) {
            dp[rows -1][col] = dp[rows - 1][col + 1] - dungeon[rows - 1][col];
            setMinHP(dp, rows - 1, col);
        }

        for (int row = rows - 2; row >= 0 ; row--) {
            for (int col = cols - 2; col >= 0; col--) {
                dp[row][col] = Math.min(dp[row][col + 1], dp[row+1][col]) - dungeon[row][col];
                setMinHP(dp, row, col);
            }
        }

        return dp[0][0];
    }

    private void setMinHP(int[][] dp, int row, int col) {
        if (dp[row][col] < 1) {
            dp[row][col] = 1;
        }
    }
}
